//* inorder binary tree traversal 
#include <iostream>
#include <stack>
#include "tree_traversal.h"

//* recursive 
void inorder_traverse_recursive(Node *root)
{
	if(root) {
		inorder_traverse_recursive(root->left);
		std::cout << root->key << ' ';
		inorder_traverse_recursive(root->right);
	}
}

//* three cases
//* terminate when curr == root->parent;
void inorder_traverse_iterative(Node *root)
{
	Node *curr = root;
	Node *last = 0;
	while (curr) {
		if (curr->parent == last) { //traverse down
			last = curr;
			if (curr->left) { //if curr has left child
				curr = curr->left;
			}
			else { //if curr doesn't have left child
				std::cout << curr->key << ' ';
				if (curr->right) 
					curr = curr->right;
				else
					curr = curr->parent;
			}
		}
		else if (curr->left == last) { //traverse up from left child
			last = curr;
			std::cout << curr->key << ' ';
			if (curr->right)
				curr = curr->right;
			else
				curr = curr->parent;
		}
		else if (curr->right == last) {
			last = curr;
			curr = curr->parent;
		}
	}
}

void inorder_traverse_iterative2(Node *root) {
	Node *curr = root;
	Node *prev = curr->parent;
	while(curr != nullptr) {
		if (curr->left == nullptr || prev == curr->left) {
			prev = curr;
			std::cout << curr->key << ' ';
			if(curr->right == nullptr) 
				curr = curr->parent;
			else
				curr = curr->right;
		}
		else if (prev == curr->parent) {
			prev = curr;
			curr = curr->left;
		}
		else if (prev == curr->right) {
			prev = curr;
			curr = curr->parent;
		}
	}
}

void inorder_traverse_with_stack(Node* root) {
	Node* curr = root;
	std::stack<Node*> s;
	while(curr != nullptr) {
		if (curr->left && !curr->left->visited) { //visit left child
			s.push(curr);
			curr = curr->left;
			continue;
		}
		std::cout << curr->key << ' '; // visit current node
		curr->visited = true;
		if(curr->right && !curr->right->visited) { //visit right child
			curr = curr->right;
			continue;
		}
		if(!s.empty() ) {
			curr = s.top();
			s.pop();
		}
		else
			break;
	}
}

void inorder_travers_with_stack_without_visit(Node* root) {
	Node* curr = root;
	std::stack<Node*> s;
	while(curr != nullptr || !s.empty()){
		if(curr!= nullptr) {
			s.push(curr);
			curr = curr->left;
		}
		else {
			curr = s.top();
			s.pop();
			std::cout << curr->key << ' '; // visit current node
			curr = curr->right;
		}
	}
}


